public class Test4 {
    //leetcode 918 环形子数组的最大和
    public int maxSubarraySumCircular(int[] nums) {
        //这个题目因为数组是环形数组，如果我们只用dp[i]表示以i位置为结尾的所有子数组中的最大和的话，
        //那么环形数组的情况就无法考虑到了，所以我们还需要使用一个dp表来记录以i位置为结尾的所有子数组中
        //的最小和，最后使用nums数组中所有元素的和减去这个最小值就考虑了环形数组的情况
        int n = nums.length;
        int[] f = new int[n],g = new int[n];
        f[0] = g[0] = nums[0];
        int max = nums[0], min = nums[0], sum = nums[0];
        for (int i = 1; i < n; i++) {
            sum += nums[i];
            f[i] = Math.max(nums[i],f[i-1] + nums[i]);
            g[i] = Math.min(nums[i],g[i-1] + nums[i]);
            max = Math.max(max,f[i]);
            min = Math.min(min,g[i]);
        }
        return min == sum ? max : Math.max(max,sum-min);
    }

    public static void main(String[] args) {
        Test4 test4 = new Test4();
        int[] arr = {5,-3,5};
        test4.maxSubarraySumCircular(arr);
        System.out.println(666);
    }
}
